/****************************  LABELLIB.C  ******************************/
#ifndef _LABELLIBC_
#define _LABELLIBC_

#include "stdafx.h"

#include <stdio.h>
#include <stdlib.h>



#include "basic.h"
#include "LABELLIB.H"
//#include "macro.h"

/**********************  GETNEIGHBORTABLE  **************************/
/* Find every subblock and the relations between them */
NEIGHBORDATATYPE GetNeighborTable(LABELDATATYPE *array, int RowLen, int ColLen,
                          NEIGHBORDATATYPE neighbor[2*MAXLINK], NEIGHBORDATATYPE *TemArray,
                          unsigned *TabLen, TmpAreaDATATYPE area[MAXSUBBLOCK+1])
{
  int        StartPos, EndPos, GrayNoLastLine;
  int         h, i, j, k, m, n;
  int        *pGray;
  NEIGHBORDATATYPE GrayNo;
  static int  Gray[MAXSLINK];

  pGray = &(Gray[0]);
  for(i=0;i<MAXSLINK;i++,pGray++) 
	  *pGray = 0;

  GrayNo  = 0;
  *TabLen = 0;

  /* Set the margin of the image be zero */
  /*
  for (i=0; i<RowLen; i++)
  {
    array[i][0] = 0;
    array[i][ColLen-1] = 0;
  }
  for (j=0; j<ColLen; j++)
  {
    array[0][j] = 0;
    array[RowLen-1][j] = 0;
  }
  */

  i=0,j=0,h=0;
  for (i=0; i<RowLen; i++)
  {
	  for (j=0; j<ColLen; j++)
	  {
		  if (array[i*ColLen+j]!=0)
		  {
			StartPos =j;
			do                          
			{ 
			  j++;
			  if (j==ColLen)  break;    
			} while (array[i*ColLen+j]!=0); 
			EndPos = j-1;

			GrayNoLastLine = 0;
			for (k=StartPos-1; k<=EndPos+1; k++)
			{
			  if (i-1<0)  break;   //  For the first line
			  if ((k<0)||(k>=ColLen))  continue;  
			  if ( TemArray[(i-1)*ColLen+k]!=0 )
			  {
				if (GrayNoLastLine>=MAXSLINK)
				{
				  //printf(" Single links are too many!\n");
				  //for(m=0;m<SRow;m++)
				  //for(n=0;n<SCol;n++)
				  //RImage[m][n] = 255;
				  exit(1);
				}
				Gray[GrayNoLastLine] = TemArray[(i-1)*ColLen+k];
				GrayNoLastLine++;
				while (TemArray[(i-1)*ColLen+k]!=0) k++;
			  }
			}

			if (GrayNoLastLine==0)
			{
			  GrayNo++;
			  if (GrayNo>MAXSUBBLOCK)
			  {
				//printf("  Subblocks are too many!\n");
				//for(m=0;m<SRow;m++)
				//for(n=0;n<SCol;n++)
				  //RImage[m][n] = m << 2;
				exit(1);
			  }
			  if (*TabLen>=MAXLINK)
			  {
				//printf("  Links are too many!\n");
				//for(m=0;m<SRow;m++)
				//for(n=0;n<SCol;n++)
				  //RImage[m][n] = m << 2;
				exit(1);
			  }
			  neighbor[*TabLen] = GrayNo;
			  neighbor[*TabLen+MAXLINK] = GrayNo;
			  (*TabLen)++;
			  area[GrayNo] = EndPos - StartPos + 1;
			  for (k=StartPos; k<=EndPos; k++)
				TemArray[i*ColLen+k] = GrayNo;
			}
			else
			{
			  for (k=StartPos; k<=EndPos; k++)
				TemArray[i*ColLen+k] = Gray[0];
			  area[Gray[0]] += EndPos - StartPos + 1;
			  for (k=1; k<GrayNoLastLine; k++)
			  {
				if (*TabLen>=MAXLINK)
				{
				  //printf("  Links are too many!\n");
				  //for(m=0;m<SRow;m++)
				  //for(n=0;n<SCol;n++)
					//RImage[m][n] = 255;
				  exit(1);
				}
				neighbor[*TabLen] = Gray[0];
				neighbor[*TabLen+MAXLINK] = Gray[k];
				(*TabLen)++;
			  }
			}
		  }
	  }
  }

  return(GrayNo);
}

/**********************  GETMAPTABLE  ****************************/
/*  From all subblocks and the relations between them to find the true
    blocks
*/
unsigned GetMapTable(NEIGHBORDATATYPE neighbor[2*MAXLINK], unsigned TabLen,
                     NEIGHBORDATATYPE map[MAXSUBBLOCK+1])
{
  static NEIGHBORDATATYPE  stack[MAXSLINK];
  unsigned   i, j, TrueObj, StackPtr, TmpValue;
  NEIGHBORDATATYPE *pstack,*pneighbor0,*pneighbor1,*pneighbor2,*pneighbor3;

  pstack = &(stack[0]);
  for(i=0;i<MAXSLINK;i++,pstack++)  *pstack = 0;

  TrueObj  = 0;
  StackPtr = 0;

  pneighbor0 = &(neighbor[0]);
  pneighbor1 = &(neighbor[MAXLINK]);

  for (i=0; i<TabLen; i++,pneighbor0++,pneighbor1++)
  {
    if (*pneighbor0!=0)
    {
      stack[StackPtr] = *pneighbor0;
      StackPtr++;
      TrueObj++;
      *pneighbor0 = 0;
      *pneighbor1 = 0;
    }

    while (StackPtr!=0)
    {
      StackPtr--;
      TmpValue = stack[StackPtr];
      map[TmpValue] = TrueObj;

      pneighbor2 = pneighbor0;
      pneighbor3 = pneighbor1;

      for (j=i; j<TabLen; j++, pneighbor2++, pneighbor3++)
        if ((*pneighbor2 == TmpValue) || (*pneighbor3 == TmpValue))
        {
          if (*pneighbor2!=*pneighbor3)
          {
            stack[StackPtr] = (*pneighbor2!=TmpValue)? *pneighbor2
                                                        : *pneighbor3;
            StackPtr++;
          }
          *pneighbor2 = 0;
          *pneighbor3 = 0;
        }
    }
  }
  return(TrueObj);
}

/************************  MODIFYMAPTABLE1  ***************************/
/* Use the Minarea to find the true objects */
int ModifyMapTable1(NEIGHBORDATATYPE map[MAXSUBBLOCK+1], TmpAreaDATATYPE area[MAXSUBBLOCK+1], NEIGHBORDATATYPE GrayNo,
                    unsigned TrueObj, int MinArea)
{
  int TrueTrueObj;
  int i, j, m, n;
  unsigned TmpArea;

  NEIGHBORDATATYPE *pmap;
  TmpAreaDATATYPE *parea;

  TrueTrueObj = 0;
  for (i=1; i<=TrueObj; i++)
  {
    TmpArea = 0;

    pmap  = &(map[1]);
    parea = &(area[1]);

    for (j=1; j<=GrayNo; j++, pmap++, parea++)
      if (*pmap==i)
        TmpArea += *parea;

    if (TmpArea<MinArea)
    {
      pmap  = &(map[1]);

      for (j=1; j<=GrayNo; j++, pmap++)
        if (*pmap==i)
          *pmap = 0;
    }
    else
    {
      TrueTrueObj++;
      if (TrueTrueObj>MAXBLOCK)
      {
        //printf("  Blocks are too many!\n");
        //for(m=0;m<SRow;m++)
        //for(n=0;n<SCol;n++)
          //RImage[m][n] = 255;
        exit(1);
      }

      pmap  = &(map[1]);

      for (j=1; j<=GrayNo; j++, pmap++)
        if (*pmap==i)
          *pmap = TrueTrueObj;
    }
  }

  return(TrueTrueObj);
}

/************************  MODIFYMAPTABLE2  ***************************/
/* Let the max block to be the true objects */
void ModifyMapTable2(NEIGHBORDATATYPE map[MAXSUBBLOCK+1], TmpAreaDATATYPE area[MAXSUBBLOCK+1], NEIGHBORDATATYPE GrayNo,
                     unsigned TrueObj)
{
  int MaxBlockNo;
  int i, j;
  unsigned MaxBlockArea;
  static TmpAreaDATATYPE TmpArea[MAXBLOCK+1];
  long Tmp = 0;

  for(i=0;i<MAXBLOCK+1;i++)  TmpArea[i] = 0;

  /* Get the area of all blocks */
  for (i=1; i<=TrueObj; i++)
  {
    TmpArea[i] = 0;

    for (j=1; j<=GrayNo; j++)
      if (map[j]==i)
        TmpArea[i] += area[j];
    Tmp +=  TmpArea[i];
  }

  /* Find the block number of the max block */
  MaxBlockArea = 0;
  for (i=1;i<=TrueObj;i++)
    if (TmpArea[i]>MaxBlockArea)
    {
      MaxBlockArea = TmpArea[i];
      MaxBlockNo = i;
    }

  for (i=1;i<=GrayNo;i++)
    if (map[i]!=MaxBlockNo)
      map[i] = 0;
    else
      map[i] = 1;
}

/***************************  DOMAP  *****************************/
/* Label the true objects */
/*void DoMap(NEIGHBORDATATYPE **array, unsigned **TemArray, int RowLen, int ColLen,
           unsigned map[MAXSUBBLOCK+1])
{
  int i, j;

  NEIGHBORDATATYPE *parray = &(array[0][0]);
  unsigned      *pTemArray = &(TemArray[0][0]);

  map[0] = 0;
  //for (i=1; i<RowLen-1; i++)
    //for (j=1; j<ColLen-1; j++)
  for (i=0; i<RowLen; i++)    //
    for (j=0; j<ColLen; j++, parray++, pTemArray++)  //
      if (map[*pTemArray]!=0)
        *parray = MAXGREYLEVEL - map[*pTemArray] + 1;
      else
        *parray = 0;
}*/

void DoMap(LABELDATATYPE *array,NEIGHBORDATATYPE *TemArray,  int RowLen,  int ColLen,
           NEIGHBORDATATYPE map[MAXSUBBLOCK+1], int maxgraylevel)
{
	int i, j;
	NEIGHBORDATATYPE  *pTemArray = &(TemArray[0]);
	LABELDATATYPE   *parray = &(array[0]);
	
	map[0] = 0;
	
	for (i=0; i<RowLen*ColLen;i++,parray++, pTemArray++)    
		if (map[*pTemArray]!=0)
			*parray = maxgraylevel - map[*pTemArray] + 1;
		else
			*parray = 0;
}


/****************************  LABEL  ****************************/
/*  LabelMode = LABELMODE_1, Use the Minarea to find the true objects */
/*  LabelMode = LABELMODE_2, Let the max block to be the true objects */
/*  MinArea is only used when LabelMode is LABELMODE_1                */
int Label(LABELDATATYPE *array, int RowLen,  int ColLen, int LabelMode,  
                                int MinArea, int maxgraylevel)
{
  static NEIGHBORDATATYPE   map[MAXSUBBLOCK+1],neighbor[2*MAXLINK];
  static TmpAreaDATATYPE TmpArea[MAXSUBBLOCK+1];
  static NEIGHBORDATATYPE   *TemArray;    
  unsigned   TabLen, GrayNo, TrueObj;
  NEIGHBORDATATYPE   *pmap, *pneighbor, *pTemArray;
  TmpAreaDATATYPE *pTmpArea;
  int        i, j;

  TemArray =(NEIGHBORDATATYPE *)fspace_1d(RowLen*ColLen,sizeof(NEIGHBORDATATYPE));
  pmap     = &(map[0]);
  pTmpArea = &(TmpArea[0]);
  
  for(i=0;i<MAXSUBBLOCK+1;i++,pmap++,pTmpArea++)
    *pmap = *pTmpArea = 0;

  pneighbor = &(neighbor[0]);
  for(i=0;i<2*MAXLINK;i++,pneighbor++)
      *pneighbor = 0;

  pTemArray = &(TemArray[0]);
  for(i=0;i<RowLen*ColLen;i++,pTemArray++)
    *pTemArray = 0;

  GrayNo = GetNeighborTable(array, RowLen, ColLen, neighbor, TemArray, &TabLen,
                            TmpArea);  //???neighbor

  if (GrayNo>MAXSUBBLOCK)
  {
      exit(1);
  }

  if (GrayNo==0)
  {
      return(0);
  }

  TrueObj = GetMapTable(neighbor, TabLen, map);  

  if (LabelMode==1)
  {
    TrueObj = ModifyMapTable1(map, TmpArea, GrayNo, TrueObj, MinArea);
  }
  else
  {
    ModifyMapTable2(map, TmpArea, GrayNo, TrueObj);
    TrueObj = 1;
  }

  //DoMap(array, TemArray, RowLen, ColLen, map);
  DoMap(array, TemArray, RowLen, ColLen, map,maxgraylevel);
  
	ffree_1d((void *)TemArray);
  return(TrueObj);
}

#endif
/**************************  END OF LABELLIB.C  *************************/
